A conventional design process for an integrated circuit, such as an ASIC or a circuit to be implemented on a field programmable gate array (FPGA) or other programmable logic device, begins with the creation of the design. The design specifies the function of a circuit at a schematic or logic level and may be represented using various programmable languages (e.g., VHDL, ABEL or Verilog) or schematic capture programs. The design is synthesized to produce a logical network list (“netlist”) supported by a target integrated circuit device. The synthesized design is mapped to primitive components within the target device (e.g., programmable logic blocks of an FPGA).
Following mapping, placement of the components of the synthesized and mapped design is then performed for the target device. During placement, each mapped component of the design is assigned to a physical position on the chip. One objective of the placer is to place connected design objects in close physical proximity to one another. This conserves space on the chip and increases the probability that the desired interconnections between components will be successfully completed by the router. Placing connected components close to one another also generally improves the performance of the circuit, since long interconnect paths are associated with excess capacitance and resistance, resulting in longer delays.
Specified connections between components of the design are routed within the target device for the placed components. Routing specifies physical wiring resources that will be used to conduct signals between pins of placed components of the design. For each connection specified in the design, routing must allocate wiring necessary to complete the connection. As used herein, the selection and assignment of wire resources in connecting the output pin of one component to the input pin of another component is referred to as routing a signal. When signals have been routed using most or all of the wiring resources in a given area, the area is generally referred to as congested, which creates competition for the remaining wiring resources in the area or makes routing of additional signals in the area impossible. A routing solution free of congestion may be referred to as a congestion-free solution or a non-conflicting routing solution, and such terms may be used interchangeably herein.
Once a routing solution is found, some routing procedures also involve post-routing optimization methods to improve a circuit's timing, power consumption, routing resources utilized, and any combination thereof. In some instances, timing-based estimations of the design are also provided.
The circuit design process generally includes functional and timing simulations to verify correct operation prior to manufacturing. A design may be modified several times to correct errors identified during testing. Whenever a modification is made, the place-and-route procedures must be repeated for the modified design. Due to the large amount of time required for placement and routing of an entire design, it is desirable to avoid repeating the entire place-and-route process when only a small portion of the design has changed.
A design may be modified several times throughout the development process. One solution to avoiding the repeating of the entire process of optimization and place-and-route is to perform place-and-route with criteria to preserve placed and routed portions of the design, which are not changed. This is known as incremental placement and routing. Current incremental routing methods continue routing until a routing solution is found that is non-conflicting and meets timing requirements for all signals. Due in-part to the large number of possible routing solutions, current incremental place-and-route methods often make early non-optimal routing choices and fail to review those early routing choices, which may constrict the algorithm to a non-optimal local maxima.
Due to congestion resulting from these early routing choices, it may not be possible to route the modified signals of the design and meet all timing requirements without rerouting some signals of the unchanged portion of the design. While the routing algorithm attempts to preserve routing of the routed signals as much as possible, routed signals are often re-routed in an attempt to remove congestion or improve timing performance of other signals. However, some of the routed signals may have strict timing requirements that are difficult to meet. These signals are referred to as critical signals. Once unrouted, it may be difficult to find an alternative route that meets these strict timing requirements. In addition, previous optimization of these signals will likely be lost once the signals are rerouted. As a result, a design that previously met timing requirements may no longer meet the same timing requirements after incorporating latest design changes.
The number of rerouted signals along with the resulting timing may depend largely on the early routing choices of the algorithm, producing unpredictable results in performance. As a result, routing may need to be repeated a number of times before an acceptable routing result is be achieved. The failure to (or the variability to) achieve timing closure after an incremental revision of the design may increase the overall number of implementation iterations (or total runtime) needed to produce a feasible solution that meets all requirements and thereby result in a negative consumer experience.
One or more embodiments may address one or more of the above issues.